package com.tianyuan.test2;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
/**
 * 包含min函数的栈
 *
 * @date 2025/10/17 11:25
 * 定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数，
 * 输入操作时保证pop、top和min函数操作时，栈中一定有元素。
 *
 * 此栈包含的方法有：
 * push(value):将value压入栈中   pop():弹出栈顶元素
 * top():获取栈顶元素   min():获取栈中最小元素
 *
 * 数据范围：操作数量满足0≤n≤300，输入的元素满足|val|≤10000
 * 进阶：栈的各个操作的时间复杂度是O(1)，空间复杂度是O(n)
 *
 * 输入: ["PSH-1", "PSH2","MIN", "TOP", "POP", "PSH1", "TOP", "MIN"]
 * 输出：-1,2,1,-1
 *
 * 解析：
 * "PSH-1"表示将-1压入栈中，栈中元素为-1
 * "PSH2"表示将2压入栈中，栈中元素为2,-1
 * “MIN”表示获取此时栈中最小元素==>返回-1
 * "TOP"表示获取栈顶元素==>返回2
 * "POP"表示弹出栈顶元素，弹出2，栈中元素为-1
 * "PSH1"表示将1压入栈中，栈中元素为1，-1
 * "TOP"表示获取栈顶元素==>返回1
 * “MIN”表示获取此时栈中最小元素==>返回-1
 */

public class Solution {
    // 栈1：nodeStack，存储所有压入的元素（核心数据栈）
    Stack<Integer> nodeStack = new Stack<>();
    // 栈2：minStack，存储“对应nodeStack状态下的最小元素”（辅助栈）
    // 特点：minStack的栈顶元素，永远是当前nodeStack中所有元素的最小值
    Stack<Integer> minStack = new Stack<>();
    /**
     * 压栈操作：将元素压入栈顶
     * @param node 要压入的元素
     */
    public void push(int node) {
        // 1. 先将元素压入核心数据栈nodeStack
        nodeStack.push(node);
        // 2. 处理辅助栈minStack：确保其栈顶始终是当前最小值
        if (minStack.isEmpty()) {
            // 若minStack为空（首次压栈），直接将当前元素压入——此时它就是唯一的最小值
            minStack.push(node);
        } else {
            // 若minStack不为空，计算“当前元素”和“minStack栈顶元素（之前的最小值）”的较小值
            int min = Math.min(node, minStack.peek());
            // 将这个“新的最小值”压入minStack——保证minStack栈顶始终是当前nodeStack的最小值
            minStack.push(min);
        }
    }
    /**
     * 出栈操作：弹出栈顶元素
     * 关键：nodeStack和minStack要"同步出栈"——保持两者状态一致
     */
    public void pop() {
        // 两个栈同步弹出栈顶元素
        // 原因：nodeStack弹出一个元素后，其状态变化，minStack对应的“旧最小值”也需同步移除（因为添加时也同步，保证minStack的栈顶元素始终是最小）
        nodeStack.pop();
        minStack.pop();
    }
    /**
     * 获取栈顶元素（仅查看，不弹出）
     * @return 当前栈顶元素（即nodeStack的栈顶元素）
     */
    public int top() {
        // 直接返回核心数据栈nodeStack的栈顶元素
        return nodeStack.peek();
    }
    /**
     * 获取当前栈中的最小元素（时间复杂度O(1)）
     * @return 栈中最小元素
     */
    public int min() {
        // 直接返回辅助栈minStack的栈顶元素——因为它始终存储当前nodeStack的最小值
        return minStack.peek();
    }







    // 测试main方法：模拟示例输入操作，输出结果
    public static void main(String[] args) {
        Solution minStack = new Solution();
        // 示例输入的操作数组
        String[] operations = {"PSH-1", "PSH2", "MIN", "TOP", "POP", "PSH1", "TOP", "MIN"};
        // 存储MIN和TOP操作的结果（POP无返回值，不存储）
        List<Integer> output = new ArrayList<>();
        // 遍历每个操作，执行对应逻辑
        for (String op : operations) {
            if (op.startsWith("PSH")) {
                // 1. 处理压栈操作：PSH后接数字（可能是负数，如PSH-1）
                int value = Integer.parseInt(op.substring(3)); // 截取"PSH"后的字符转数字
                minStack.push(value);
                System.out.printf("执行操作：%s → 压入元素%d，当前nodeStack：%s，minStack：%s%n",
                        op, value, minStack.nodeStack, minStack.minStack);
            } else if (op.equals("POP")) {
                // 2. 处理出栈操作：无返回值，仅同步弹出
                minStack.pop();
                System.out.printf("执行操作：%s → 弹出栈顶元素，当前nodeStack：%s，minStack：%s%n",
                        op, minStack.nodeStack, minStack.minStack);
            } else if (op.equals("TOP")) {
                // 3. 处理获取栈顶操作：记录结果
                int topVal = minStack.top();
                output.add(topVal);
                System.out.printf("执行操作：%s → 栈顶元素为%d，当前nodeStack：%s%n",
                        op, topVal, minStack.nodeStack);
            } else if (op.equals("MIN")) {
                // 4. 处理获取最小值操作：记录结果
                int minVal = minStack.min();
                output.add(minVal);
                System.out.printf("执行操作：%s → 栈中最小元素为%d，当前minStack：%s%n",
                        op, minVal, minStack.minStack);
            }
        }
        // 打印最终输出结果（与示例预期对比）
        System.out.println("\n最终输出结果：" + output);
        System.out.println("示例预期结果：[-1, 2, 1, -1]");
    }
}